public class 满足不等式的最大值 {
    public static int MAXN = 100001;
    public static int[][] deque = new int[MAXN][2] ; // 0 为下标, 1 为 y - x
    public static int h,t;
    public int findMaxValueOfEquation(int[][] points, int k) {
        h = t = 0;
        int ans = Integer.MIN_VALUE; // 有可能为负数, ans 初始化不能为 0
        for (int r = 0; r < points.length; r++) {
            int x = points[r][0]; // 当前点的 x
            int y = points[r][1]; // 当前点的 y
            // 判断维护的头节点和现节点的 x 差值是否会超过 k
            // 如果超过, 就弹出头节点, 直到队列为空
            while (h < t && x - points[deque[h][0]][0] > k) {
                h++;
            }
            // 如果单调队列中有满足的元素, 就记录元素的最大值
            if (h < t) {
                ans = Math.max(ans,deque[h][1] + x + y);
            }
            // 将当前元素进行入队操作, 遇到小于当前元素的就弹出, 直到队列为空 或 找到更大的值入队
            while (h < t && deque[t - 1][1] <= y - x) {
                t--;
            }
            deque[t][0] = r;
            deque[t++][1] = y - x;
        }
        return ans;
    }
}
